The invention relates to a method for the polling of queues, each having a number of queue elements which varies in time and is not known in advance, which method involves forming, from queue values such as the numbers of elements in the various queues or the increase in those numbers of queue elements, a ratio table having ratio values which represent these queue values, which ratio table is subsequently converted into a polling sequence table with a polling sequence which is as regular as possible. This is particularly applicable to the polling of ATM data cells. Such a method is known from, amongst others, a publication entitled Optimizing Of Polling Systems, as authored by O. J. Boxima et al, Report BS-R8932, Centre for Mathematics and Computer Science, P.O. Box 4079, NL-1009AB Amsterdam. The method presented there comprises a number of steps, namely:
Step 1: using queue characteristic values for the various queues, such as the queue size or queue growth, the `occurrence ratio` (eg. occurrence frequency), is calculated for each queue; PA1 Step 2: using the ratios thus calculated, the polling table size M and the absolute number of occurrences per queue are calculated; PA1 Step 3: using the calculated table size M and the calculated numbers of occurrences per queue, the polling sequence of the various queues is calculated. PA1 Step 1: calculate the ratio values R(n) in the ratio table using the queue values Q(n); PA1 Step 2: calculate the sum S of these ratio values R(n); PA1 Step 3: assign to each queue x a correction factor C(x) which is equal to said sum S of the ratio values, decreased by the ratio value R(x) of that queue x; PA1 Step 4: select the queue i having the highest urgency factor U(i) or, if more queues have this highest urgency factor U(i), select one specific queue i therefrom, for example the first queue occurring in the ratio table having this highest urgency factor U(i); PA1 Step 5: reduce the urgency factor U(i) of that selected queue i by the value of its correction factor C(i); PA1 Step 6: increase the urgency factor U(x) of the remaining queues (.noteq.i) by their ratio value R(x); PA1 Step 7: repeat from step 4 or repeat from step 1 (see below).
In step 3, use is made of a `random control policy` or of a `golden ratio policy`, both taken from studies as reported by Hofri & Rosberg in the article entitled Packet Delay Under the Golden Ratio Weighted TDM Policy in a Multiple-Access Channel, IEEE Trans. Inform. Theory, Vol. IT-33, pp. 341-349. The performance of the `random policy` is quite limited. The performance of the `golden ratio policy` is better, though it requires quite complex mathematical operations, which take a relatively large amount of time, which is quite a significant disadvantage for the handling of ATM data cells which after all, are intended for broadband applications such as B-ISDN.